package datastructure_algorithm.heap;

import java.util.Arrays;

public class MaxHeap<Item extends Comparable> {
	
	protected Item[] data;
	protected int count;
	private int capacity;
	
	public MaxHeap(int capacity) {
		data = (Item[]) new Comparable[capacity + 1];
		count = 0;
		this.capacity = capacity;
	}
	
	public int size() {
		return count;
	}
	
	public boolean isEmpty() {
		return count == 0;
	}
	
	public void insert(Item item) {
		assert count + 1 <= capacity;
		data[count + 1] = item;
		count++;
		shiftUp(count);
	}
	
	public Item extractMax() {
		assert count > 0;
		Item ret = data[1];
		swap(1, count);
		count--;
		shiftDown(1);
		return ret;
	}
	
	private void shiftDown(int k) {
		while(2*k <= count) {
			int j = 2*k;
			if(j + 1 <= count && data[j+1].compareTo(data[j]) > 0) {
				j++;
			}
			if(data[k].compareTo(data[j]) >= 0) {
				break;
			}
			swap(k, j);
			k = j;
		}
		
	}

	private void shiftUp(int k) {
		while(k > 1 && data[k/2].compareTo(data[k]) < 0) {
			swap(k, k/2);
			k /= 2;
		}
	}

	private void swap(int i, int j) {
		Item t = data[i];
		data[i] = data[j];
		data[j] = t;
		
	}
	
	@Override
	public String toString() {
		return Arrays.toString(data);
	}

	public static void main(String[] args) {
		MaxHeap<Integer> maxHeap = new MaxHeap<>(100);
		int N = 10;
		int M = 100;
		for(int i = 0; i < N; i++) {
			maxHeap.insert(new Integer((int) (Math.random() * 100)));
		}
		
		System.out.println(maxHeap.toString());
		
		while(!maxHeap.isEmpty()) {
			System.out.print(maxHeap.extractMax() + " ");
		}
	}
	
}
